package maze;

import java.util.ArrayList;
import java.util.Set;
import java.util.TreeSet;

/**
 * Internal representation of the maze.
 * 
 * Can be added to, traversed backwards, etc.
 * Here, "node"/"intersection" and "maze"/"graph" are interchangeable.
 *
 * Development stage: experimental.
 * 
 * Notes:
 * This can be thought of as a graph-like linked structure
 *  with a variable pointer... things can be added to the current location.
 * @author Calvin
 */
class Maze {
	/**
	 * This is the root of the graph (ok, graphs don't have roots, but bear with me).
	 */
	private Node start;
	/**
	 * Pointer to the current working location in the maze, that is, the node whose neighborhood
	 * the robot is exploring (to use graph theory speak).
	 */
	public Node base;
	
	/**
	 * Pointer to the current physical location of the bot (must be synced, obviously). Should be
	 * one of {@link #base}'s neighbors (graph theory-wise).
	 */
	public Node current;
	
	/** @deprecated New {@link #base}s should be picked from the {@link #open} set.
	 * The set of all nodes (used when picking a new {@link #base}).
	 */
	public Set<Node> all;
	
	/**
	 *  The "open set" in A* parlance.
	 *  
	 *  This stores all possibilities for the next {@link #base}. It is
	 *  a TreeSet to make it easier to pick the optimal one
	 */
	public TreeSet<Node> open;
	
	/**
	 * A* can be optimized via the use of a "closed set". I'm not entirely sure
	 * what the use of it is. Wikipedia sez,
	 * "The closed set can be omitted (yielding a tree search algorithm) if a solution
	 * is guaranteed to exist, or if the algorithm is adapted so that new nodes are added
	 * to the open set only if they have a lower f value than at any previous iteration."
	 */
	public Set<Node> closed;
	
	public Maze(ArrayList<Direction> initialDirs){
		open = new TreeSet<Node>();
		//closed = new HashSet<Node>(); // ???
		
		/*
		 * Some nitty-gritty implementation details have to be explained here.
		 * 
		 * Dijkstra's algorithm is basically A* with a fixed heuristic value
		 * (since it isn't used). I haven't given up hope of finding a heuristic,
		 * and Dijkstra's can be considered a special case of A*, so I have both
		 * g() and h() values here. g() values will be computed as the node is added
		 * to the Maze. Node.UNKNOWN_H will be used for nodes which do not have a
		 * computed h() value. This does not preclude putting one in later.
		 */
		start = new Node(0.0, Node.UNKNOWN_H, initialDirs);
		base = current = start;
	}
	
	/**
	 * Add a new node to the maze.
	 * @param path The path from the current working location to the new node.
	 * @param node The new node. This should have g- and h-vals already set (i.e.,
	 *             this does not take care of that stuff)
	 *             
	 * This does not change the current pointer.
	 */
	public void add(Vector path, Node node){
		current.addNeighbor(node, path);
		all.add(node);
	}
	
	/**
	 * Update {@link #current} after a bot move.
	 * 
	 * Precondition: current.neighbors.get(dir) != null (i.e., the neighbor specified exists)
	 */
	public void movedToward(Direction dir){
		current = current.neighbors.get(dir);
	}
}